A wireless communication network typically includes a wireless client device or station (STA) that communicates with one or more access points (APs) that are connected to a communications infrastructure. The communications infrastructure typically consists of routing nodes which facilitate the movement of message packets through wired or wireless network connections. In a typical wireless infrastructure system, a STA may roam within the network by association and disassociating with multiple APs. However, typically APs and the associated network topology remain stationary and static.
FIG. 1 is a schematic diagram illustrating a conventional wireless system. The wireless network 100, in pertinent part, includes a repeater device 101 wirelessly connected via communication links 105 between two client devices 102 and an access point 104. The access point 104 is also connected through a wired network connection 107 to the LAN 106. Additionally, an administrator 103 communicates with the wireless network through the LAN 106 via the wired network connection 108. In FIG. 1, the wireless network 100 is extended using the repeater device 101. However, the repeater device 101 will effectively halve the potential bandwidth if it is sending and receiving on the same channel. Therefore, uninterrupted data streams passing both in and out of a repeater can only use, at most, half the available bandwidth on the channel.
Another type of wireless network, known as a mobile ad hoc network (MANET) enables the routing nodes to move and form a dynamic autonomous network with an arbitrary topology. In this type of wireless network, a STA may also function as a routing node and not be required to associate with an AP. A MANET is also referred to as a “multi-hop network” because multiple wireless transmission hops may be necessary to forward message packets between nodes in the network.
MANETs are attractive because they provide instant network formation without the need for connection planning and routing node administration. The result is ease of deployment, speed of deployment, and decreased dependence on a fixed infrastructure. However, a MANET must overcome numerous obstacles to effective communications. For example, nodes are mobile and connected dynamically in an arbitrary manner based on the proximity of one node to another and are therefore subject to frequent disconnection. Wireless links have significantly lower capacity than wired links because they are affected by additional error sources that result in degradation of the received signal and high bit error rates. Mobile nodes may rely on battery power and therefore be energy constrained. Mobile nodes are more autonomous and less capable of centralized administration. The mobile nodes in a network must share common radio frequencies and are therefore prone to greater interference from each neighboring node.
One important network component is its routing protocol. The routing protocol is the mechanism by which message packets are directed and transported through the network from the message source to its destination. An important routing protocol objective is to maximize network performance while minimizing the cost of the network itself in accordance with its capacity. Dynamic connections and the arbitrary manner in which nodes are connected in a MANET create a challenge to the routing method. Factors which impact the ability of the routing protocol to accomplish its objectives include hop count, delay, throughput, loss rate, stability, jitter, density, frequency of communications, and frequency of topology changes (mobility rate).
The routing protocol must also guard against message packet duplication and communication loops. For example, if two network nodes, A and B, were to retransmit every message packet they received; A would first send a message packet to B which would then retransmit it back to A, and so on. Any new message packets introduced into the network would also loop and eventually the network would be completely saturated with continuously looping message packets. Loop prevention methods such as Spanning Tree Protocol (STP), as described by IEEE 802.1 d, address this problem while allowing for path redundancy.
However, STP and its variants, such as Rapid Spanning Tree Protocol and Multiple Spanning Trees Protocol, do not perform well in networks where the quality or availability of connections between routing nodes is dynamic and subject to frequent change. For example, STP relies upon a root node to organize and create a logical tree that spans all of the nodes in the network with only one active path. This routing pathway information is disseminated from the root node to all other routing nodes. Any changes to the network topology, including changes in link quality and the addition or subtraction of a pathway or network node must be organized by the root node and a new logical tree created and disseminated to all routing nodes. Because of this, STP and other protocols which rely upon root node techniques do not perform well in dynamic network environments and can cause network reliability issues due to unacceptable periods of interrupted communications while the network routing is rediscovered and disseminated to all routing nodes.
In order for a routing node to forward a message packet, the routing protocol must know the network address of the next network node in the message packet's path. Network addresses can either be explicitly stated in the header or wrapper of the message packet, or predetermined and maintained in a table by each routing node. In the former, called source routing, there is no need to maintain a table at every routing node because every packet contains the address of every network node the packet needs to traverse. In the latter, called table-driven routing, the next routing node address is taken from a table based on the packet destination address and other criteria defined by a routing protocol. In table-driven routing, such as Optimized Link State Protocol (OLSR) and Wireless Routing Protocol (WRP), each routing node must continuously evaluate and maintain information on routes to every other node in the network and periodically exchange this information with other routing nodes.
Some MANET routing protocols include variations for on-demand routing using reactive mechanisms, where routes are found when they are needed and thus reduce the amount of overhead traffic by avoiding the need to frequently exchange state information. Additionally, there are other hybrid, hierarchical, and location-based protocols that have been proposed. Two of the better known MANET protocols are Ad hoc On-Demand Distance Vector Routing (AODV) and Dynamic Source routing (DSR). AODV is based on a distance vector routing method and uses a route table to find the next network node in the route. However, the AODV protocol assumes that each link is symmetric and is not well adapted to networks having asymmetric pathways between routing nodes. DSR is based on a source routing method and while supporting asymmetric pathways between routing nodes, it imposes the overhead of communicating the entire route map with every message packet.